A wireless multihop communications network, such as a mesh network, includes a set of nodes capable of exchanging messages with one another over a wireless medium, typically using radio frequency (RF) airwaves. Each of the nodes can be primarily a communications device or, alternatively, the communications functionality may be secondary to its primary function. For example, in a given node, the communications circuitry can be a part of a device such as a computer system, a smart appliance, a vehicle, a media device, a piece of industrial equipment (e.g., an instrument, machine, sensor, actuator), and the like.
In a mesh architecture the nodes are uniquely addressable, and able to route messages from an originating node toward the intended destination node. In general, each of the nodes can be an originating and destination node as well. Although routing can be centrally controlled, this approach requires the central controller to have an intimate knowledge of the network topology. This often presents difficulties in situations where the topology is dynamic such that nodes may join or leave the network, or have varying degrees of connectivity due to changing circumstances. Accordingly, a variety of techniques have been developed for distributed routing in which individual nodes make routing decisions based on information that they have about the current (or nearly current) state of the network.
In one type of routing algorithm, known as a link-state routing, each of the nodes constructs a map of the entire network and determines a complete or partial route for a message which that node originates based on one or more criteria for route optimization. In another approach, known as distance vector (DV) routing, each node assesses local connectivity distance to its immediate neighbors and uses the information obtained from these neighbors to construct the total path distance to other nodes in the network, without having to keep track of the actual pathways. In DV routing, an originating or forwarding node indicates which one of its neighbors should be the next hop for the message transmission. Each hop toward a particular destination node is associated with a cost. The decision of which neighbor to specify as the next hop is based on a comparison of the predetermined total costs to the destination through each of its neighbors, with the lowest-cost neighbor prevailing. Various routing mechanisms and metrics for cost estimation are disclosed and compared in Baumann, Heimlicher, Strasser, and Weibel, “A Survey on Routing Metrics,” Computer Engineering and Networks Laboratory, ETH-Zentrum, Switzerland (2007), which is incorporated by reference herein.
Regardless of which routing algorithm is used, routing metrics are needed to determine a best route. A simple distance metric is hop count, which represents the number of hops needed to reach the destination. Other known metrics are based on time delay statistics, transmission success statistics, radio link quality, and bandwidth capacity. A routing metric commonly employed in wireless mesh networks is a traffic-based metric called “Expected Transmissions Count” (ETX). ETX represents the expected (or average) number of transmissions required on a particular link to deliver a message successfully to that neighbor. This type of metric assigns a high cost to retransmitssions of failed frames, which produce consequences of reduced throughput, channel use inefficiencies, time delays, and the like, which may be more burdensome to overall network efficiency than other measures such as higher hop counts, for instance. ETX values also, to some extent, reflect radio link performance and the incidence of possible interference or obstructions, the presence of which tends to result in retransmissions, thereby increasing the ETX value for a particular link.
In a given wireless multihop network, the routing metric is typically determined by sending special probing messages between nodes, and measuring the performance of the link in delivering the probing messages. Probing messages have predetermined size and information format and content, which establishes a uniform condition to test link performance from one instance to another. In one approach, specialized probing messages are periodically sent between nodes with higher-than-normal priority in the routing queues. One drawback of these so-called out-of-band probing messages is they may not represent the network conditions that ordinary traffic experiences. In another approach, probing packets are interlaced with the regular traffic. These so-called in-band measurements contribute to the amount of traffic and network resource overhead, thereby reducing the efficiency of the network.
Probing messages are preferably sent around with some regularity, or periodicity. See, for example, Raisanen, Grotefeld, and Morton, “Network Performance Measurement with Periodic Streams,” IETF RFC 3432, (2002), incorporated by reference herein. Ideally, smaller intervals can provide insight into link performance at various times and under various conditions to provide a statistically reliable representation of the true link quality. However, small intervals require large amounts of overhead. Conversely, increasing the interval between probing messages increases the risk of missing important information. There are additional challenges of collecting balanced statistics from one node to the next in network topologies where certain nodes are much more active than others.
As an alternative to the use of probing messages, passive methods of monitoring a routing device's performance have been proposed, generally in the context of Internet traffic routers. Passive monitoring generally examines the performance of a router that operates at the packet level. Measured parameters include such measures as packet queue lengths, losses and waiting times. More advanced passive monitoring applications utilize packet sniffing, tcpdump, and polling the management information base (MIB). Although this passive approach is non-intrusive in that extra traffic is not introduced as is the case with probing packets, it suffers from not having an objective measure that probing packets provide. Since passive measures look at existing traffic, the performance data is based on packets that can vary considerably in size and content. For a wireless network, packets that are larger will naturally have more difficulty being communicated successfully than smaller packets. The passive approaches are also resource-intensive in terms of requiring considerable processing and memory overhead. This problem is not as acute in the Internet router context, where devices are line powered, and have considerable processing capacity. However, in wireless networks or networks in which the nodes are attached to low-power or low-cost devices, such computing overhead is not feasible from a technical constraint or cost constraint perspective.
In fact, wireless multihop networking is becoming increasingly ubiquitous, and is finding its way into applications in which nodes are low-bandwidth, low-cost, or low-power devices. Very often, nodes have all three of these constraints. These pressures are often coupled with the growing demands of data throughput as data sources become increasingly sophisticated. As a result of these, and other, developments, a practical and efficient solution is needed for gathering reliable routing metrics without unduly burdening the network's capacity.